Free Form Deformation (FFD) techniques have been introduced to manipulate objects in computer graphics and computer animations. The FFD has been applied to optimize shapes of aerodynamic objects in conjunction with evolutionary algorithms. The FFD techniques is known to provide a reasonable compromise in the flexibility of shapes and a small number of parameters, which in turn results in a small dimensional search space for the optimization. Furthermore, it has been demonstrated that the shape deformations defined by the FFD techniques can be applied equally well to deform a grid for computational fluid dynamics calculations. Using the FFD techniques, it is possible to obviate generating of the manual grid even for complex geometries. In many cases, design optimization of complex shapes becomes feasible only when the FFD techniques are used for the representation. In the FFD techniques, deformations of an initial design are described instead of the geometry itself. Therefore, the number of parameters is independent of the complexity of the shape and is determined solely by the required flexibility of the deformation.
An FFD system is generally defined by a lattice of control points. A modification in the positions of the control point results in a deformation of the geometry inside the control volume. For optimization, it is important to minimize the number of parameters. The reduction in the number of parameters is achieved by properly initializing the control volume because the number and position of control points determine the flexibility of the shape.
FIG. 1 is a conceptual diagram illustrating the basic idea of the FFD. The sphere of FIG. 1 represents the target object of the optimization. The target object is embedded in a lattice of control points (CP). First, the coordinates of the target object must be mapped to the coordinates in the spline parameter space, according to a procedure known as ‘freezing.’ If the object is a surface point cloud of the design or a mesh that originates from an aerodynamic computer simulation, each grid point must be converted into spline parameter space to allow the deformations. To perform this calculation, various methods have been proposed including, for example, Newton approximation or similar gradient based methods.
After freezing, the object can be modified by moving a CP to a new position. The new CP positions are the inputs for the spline equations based upon which the updated geometry is calculated. Because everything in the control volume is deformed, a grid from computational fluid dynamics that is attached to the shape is also adapted. Hence, the deformation affects not only the shape of the design but also the grid points of the computational mesh needed for the Computational Fluid Dynamics (CFD) evaluations of the proposed designs. The new shape and the corresponding CFD mesh are generated at the same time without the need for an automated or a manual re-meshing procedure. This feature significantly reduces the computational costs and allows a high degree of automation. Thus, by applying FFD the grid point coordinates are changed but the grid structure is kept intact.
One main disadvantage of the FFD method is its sensitivity to the initial placement of the control points. An inappropriate set-up increases the necessary size of the parameter set; and therefore, increases the dimensionality of the search space. One of the reasons for the inappropriate set-up is that the influence of a control point on an object decreases as the distance from the object increases. Even a small object variation requires a large modification of the control point if the initial distance between the object and the control point is large (this also violates the strong causality condition that is particularly important for Evolution Strategies). The large modification of the control point in turn often modifies other areas of the design space that has to be compensated for by moving other control points. Hence, correlated mutations of control points are often necessary for a local change of the object geometry.
To reduce the effect of the initial positions of the control points, direct manipulation is introduced as a representation that allows determination of variations directly from the shape. Therefore, local deformations of the object depend only on the so-called object points.
Direct manipulation of the free form deformations (DFFD) is an extension of the standard FFD. Instead of moving control points (CP) having effect on the shape that is not always intuitive, the designer is encouraged to modify the shape directly by specifying so-called object points (OP).
Although the initial setup of the control volume in the DFFD is similar to the FFD, the control volume becomes invisible to the user and correlated modifications are calculated analytically. In a first step, the lattice of control points is constructed and the coordinates of the object and the CFD mesh are frozen. The control volume, however, can be arbitrary. That is, the number and positions of control points do not need to have any logical relationship to the embedded object other than the fact that the number of control points determines the degree of freedom for the modification. In the next step, the designer specifies object points, which define handles to the represented object that can be repositioned. The shape is modified by directly changing the positions of these object points. The control points are determined analytically so that the shape variations (introduced by the object point variations) are realized by the deformations associated with the new control point positions. In other words, the control points are calculated in such a way that the object points meet the given new positions under the constraint of minimal movement of the control points in a least square sense. Of course the object variations must be realizable by the deformations from the newly calculated positions of the control point. That is, if the number of control points is too small, some variations given by the new position of the object may not be represented by a deformation.
FIG. 2 illustrates an object point at the top of the sphere. The designer is able to move this object point upward without any knowledge of the “underlying” control volume that may be initialized arbitrarily. The direct manipulation algorithm calculates the corresponding positions of the control points to mimic the targeted object point movement. The solution is shown in FIG. 2. The object point is chosen directly from the surface and the required movements of the control points to realize the target movement of the object point are calculated, for example, by the least squares method. The dotted control volume is invisible to the designer because the designer works directly on the object points, and the control volume may be chosen arbitrarily.
The DFFD has several advantages over the standard FFD when combined with evolutionary optimization. The construction of the control volume, and the number and distribution of control points in the DDFD are not as important as in the standard FFD. Furthermore, the number of optimization parameters equals the number of object points.
There are mainly two typical issues with the FFD. First, using the FFD, it is only possible to deform a design given initially. That is, the possible shape modifications are limited by the design which was initially chosen for deformation. Conceptual or structural changes are very difficult to achieve. For example, introduction of holes or edges is either impossible or requires a huge amount of modification to the control points.
Additionally, this process is very difficult and even impossible when dealing with designs that are not allowed to include holes in the represented space. This problem occurs when the FFD is used for deforming systems that are analyzed with computational calculation methods such as Computational Fluid Dynamics (CFD) or Finite Element Methods (FEM) to calculate specific features of the design. For example, if CFD is applied, a computational grid must be built according to the given geometry. If a hole must be introduced in the design, the hole must be meshed and be interfaced properly to the existing mesh to provide the grid for a CFD simulation. In the standard FFD method, this is not possible without a remeshing procedure that is very time consuming.
As a consequence, changes in the design are desired which provide structural design changes without holes in the represented space.
Secondly, when the FFD is applied, the design is modified by moving control points and applying the new positions of the control point to update the design. Issues often arise when control points must be moved for a significant distance to reflect a desired design change. Such moving of the control points results in a control point set that is very ill-structured because many control points are quite close to each other. If control points are very close, further design modifications are very difficult to achieve without having loops in the geometry. Therefore, a reorganization of the representation of the control points is strongly needed in order to allow further modifications to the design.